训练指南 UVA - 11478（最短路BellmanFord+ 二分+ 差分约束）

Diposting di | Edited on

Halum

UVA - 11478

题意

带权有向图，每个点都可以有如下操作：令从ta出发的每一条边增加d，终止于ta的每一条边减小d
最后让所有边权的最小值非负且尽量大

题解

考虑每条边的约束，di表示i的halum量

w-dv+du>0

dv-du<w

但求解这个差分约束系统只是让这组不等式成立，最长路和最短路控制的都是单个d的最值而不是最小值最大

那如何最小值最大呢？

二分答案……

那么不等式变为dv-du<w-mid，成立的话说明经过操作后边权可以都比mid大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2700+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct Edge
{
    int from, to;
    int dist;
    Edge() {}
    Edge(int u, int v, int d) : from(u), to(v), dist(d) {}
};
struct BellmanFord{
    int n,m;
    vector<Edge>edges;
    vector<int> G[maxn];
    bool inq[maxn]; /// 是否在队列中
    int d[maxn];    /// s到各个点的距离  double 要改成double类型
    int p[maxn];    /// 最短路中的上一条弧
    int cnt[maxn];  /// 进队次数
    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to, int dist)
    {
        edges.emplace_back(from, to, dist);
        m = edges.size();
        G[from].push_back(m - 1);
    }
    bool bellmanford(int s){
        queue<int>Q;
        memset(inq,0,sizeof(inq));
        memset(cnt,0,sizeof(cnt));
        for(int i = 0; i < n; i++) { d[i] = 0; inq[0] = true; Q.push(i); } ///如果只判负环用这个
        //for(int i=0;i<n;i++)d[i]=inf;
        //d[s]=0;inq[s]=true;Q.push(s);
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            inq[u]=false;
            for(auto& id:G[u]){
                Edge& e=edges[id];
                if(d[u]<inf && d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u] + e.dist;
                    p[e.to]=id;
                    if(!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to]=true;
                        if(++cnt[e.to]>n)return true;
                    }
                }
            }
        }
        return false;
    }
};
BellmanFord solver;
bool test(int x){
    for(int i=0;i<solver.m;i++)
        solver.edges[i].dist-=x;
    bool ret=solver.bellmanford(0);
    for(int i=0;i<solver.m;i++)
        solver.edges[i].dist+=x;
    return !ret;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    while(cin>>n>>m){
        solver.init(n);
        int ub=0;
        while(m--){
            int u,v,d;
            cin>>u>>v>>d;ub=max(ub,d);
            solver.AddEdge(u-1,v-1,d);
        }
        if(test(ub+1))cout<<"Infinite"<<endl;
        else if(!test(1))cout<<"No Solution"<<endl;
        else{
            int l=2,r=ub,ans=1;
            while(l<=r){
                int mid=(l+r)/2;
                if(test(mid)){ans=mid;l=mid+1;}
                else r=mid-1;
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}